package Utils;

import java.io.BufferedReader;
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class EditDistance {

	public ArrayList<ArrayList<String>> getSimilarResults(String[] terms) {
		//	System.out.println("Distance = " + getEditDistance(a, b));
		int minDist = Integer.MAX_VALUE;
		ArrayList<ArrayList<String>> wordsMinDist = new ArrayList<ArrayList<String>>(terms.length);
		String[] words = readFile("mydictionary.txt");
		for (int j = 0 ; j < terms.length ; j++) {
			for (String t : words) {
				int dist = getLevenshteinDistance(terms[j], t);
				if (dist < minDist) {
					minDist = dist;
					if (wordsMinDist.size() == j) {
						wordsMinDist.add(j, new ArrayList<String>());
					} else {
						wordsMinDist.remove(j);
						wordsMinDist.add(j, new ArrayList<String>());
						wordsMinDist.get(j).add(t);
					}
				} else if (dist == minDist) {
	//				System.out.println(new Integer(minDist).toString() + wordsMinDist.get(j));
					wordsMinDist.get(j).add(t);
				}
			}
			minDist = Integer.MAX_VALUE;
		}
		return wordsMinDist;
	}

	public static int getLevenshteinDistance(String s, String t) {
		if (s == null || t == null) {
			throw new IllegalArgumentException("Strings must not be null");
		}

		int n = s.length(); // length of s
		int m = t.length(); // length of t

		if (n == 0) {
			return m;
		} else if (m == 0) {
			return n;
		}

		int p[] = new int[n+1]; //'previous' cost array, horizontally
		int d[] = new int[n+1]; // cost array, horizontally
		int _d[]; //placeholder to assist in swapping p and d

		// indexes into strings s and t
		int i; // iterates through s
		int j; // iterates through t

		char t_j; // jth character of t

		int cost; // cost

		for (i = 0; i<=n; i++) {
			p[i] = i;
		}

		for (j = 1; j<=m; j++) {
			t_j = t.charAt(j-1);
			d[0] = j;

			for (i=1; i<=n; i++) {
				cost = s.charAt(i-1)==t_j ? 0 : 1;
				// minimum of cell to the left+1, to the top+1, diagonally left and up +cost				
				d[i] = Math.min(Math.min(d[i-1]+1, p[i]+1),  p[i-1]+cost);  
			}

			// copy current distance counts to 'previous row' distance counts
			_d = p;
			p = d;
			d = _d;
		} 

		// our last action in the above loop was to switch d and p, so p now 
		// actually has the most recent cost counts
		return p[n];
	}

	private static String[] readFile(String filename) {
		ArrayList<String> words = new ArrayList<String>();
		FileInputStream fstream = null;
		try {
			fstream = new FileInputStream(filename);
		} catch (FileNotFoundException e1) {
			e1.printStackTrace();
		}
		DataInputStream in = new DataInputStream(fstream);
		BufferedReader br = new BufferedReader(new InputStreamReader(in));
		String strLine;
		try {
			while ((strLine = br.readLine()) != null)   {
				words.add(strLine);
			}
		} catch (IOException e) {
			e.printStackTrace();
		}
		try {
			in.close();
		} catch (IOException e) {
			e.printStackTrace();
		}
		return words.toArray(new String[words.size()]);
	}

	
}
